﻿#define _CRT_SECURE_NO_WARNINGS 1

//动态规划第十题
//174. 地下城游戏
//https://leetcode.cn/problems/dungeon-game/description/

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();

        // 状态表示
        // dp[i][j]表示骑士的血量
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        // 假设骑士血量为x
        // 那走到第一格就是x + dungeon[0][0]
        // 要满足自己走到下一格就必须>= dungeon[0][1]或者dungeon[1][0]
        dp[m][n - 1] = dp[m - 1][n] = 1;

        // 填表
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }
};